package likou.tanxin;

import java.util.HashSet;
import java.util.Set;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/18 08:19
 */
public class _1007 {
    public static void main(String[] args) {
        System.out.println(minDominoRotations2(new int[]{1, 2, 1, 1, 1, 2, 2, 2}, new int[]{2, 1, 2, 2, 2, 2, 2, 2}));
    }

    public static int minDominoRotations(int[] A, int[] B) {
        int[] all = new int[6];
        int[] AN = new int[6];
        int n = A.length;
        for (int i = 0; i < A.length; i++) {
            AN[A[i] - 1]++;
            all[B[i] - 1]++;
            all[A[i] - 1]++;
        }
        int daan = 0;
        for (int i = 0; i < 6; i++) {
            //查看all里面是否有超过n的值
            if (all[i] >= n) {
                //让A变为目标值较多的，
                //让B变为目标值较小的
                int mubiao = i + 1;
                int[] BB = AN[i] < all[i] / 2 + all[i] % 2 ? A : B;
                A = AN[i] >= all[i] / 2 + all[i] % 2 ? A : B;
                B = BB;
                for (int j = 0; j < n; j++) {
                    if (A[j] != mubiao && B[j] != mubiao) {
                        return -1;
                    }
                    if (A[j] != mubiao && B[j] == mubiao) {
                        daan++;
                    }
                }
                return daan;
            }
        }
        return -1;
    }

    public static int minDominoRotations2(int[] A, int[] B) {
        Set<Integer> one = new HashSet<>();
        Set<Integer> two = new HashSet<>();
        int n = A.length;
        one.add(A[0]);
        one.add(B[0]);
        for (int i = 1; i < n; i++) {
            if (one.contains(A[i])) {
                two.add(A[i]);
            }
            if (one.contains(B[i])) {
                two.add(B[i]);
            }
            one = two;
            if (one.size() < 2) {
                break;
            }
            two = new HashSet<>();
        }
        if (one.size() == 0) {
            return -1;
        }
        int deep = one.iterator().next();
        int daanA = 0;
        int daanB = 0;
        for (int i = 0; i < n; i++) {
            if (A[i] != deep) {
                daanA++;
            }
            if (B[i] != deep) {
                daanB++;
            }
            if (B[i] != deep && A[i] != deep) {
                return -1;
            }
        }
        return Math.min(daanA, daanB);

    }


    /**
     * 解法3，最优解
     */
    public int minDominoRotations3(int[] A, int[] B) {
        int Ada = chick(A, B, A[0]);
        if (Ada == -1) {
            return chick(A, B, B[0]);
        }
        return Ada;
    }

    public int chick(int[] A, int[] B, int deep) {
        int n = A.length;
        int daanA = 0;
        int daanB = 0;
        for (int i = 0; i < n; i++) {
            if (A[i] != deep) {
                daanA++;
            }
            if (B[i] != deep) {
                daanB++;
            }
            if (B[i] != deep && A[i] != deep) {
                return -1;
            }
        }
        return Math.min(daanA, daanB);
    }
}
